package com.sevent;

import java.security.spec.RSAOtherPrimeInfo;
import java.util.HashSet;
import java.util.Set;

/**
 * 请编写一个方法，返回某集合的所有非空子集。
 * 给定一个int数组A和数组的大小int n，请返回A的所有非空子集。
 * 保证A的元素个数小于等于20，且元素互异。
 * 各子集内部从大到小排序,子集之间字典逆序排序
 */


public class 递归题目四_子集的生成 {
    public static void main(String[] args) {
        int[] A = {1, 2, 3};
        System.out.println(getAns2(A, A.length));

    }

    public static Set<Set<Integer>> getSubsets3(int[] A, int n) {
        // Arrays.sort(A);
        return getSubSets3Core(A, n, n - 1);
    }

    public static Set<Set<Integer>> getSubSets3Core(int[] A, int n, int cur) {
        Set<Set<Integer>> newSet = new HashSet<>();

        if (cur == 0) {
            Set<Integer> nul = new HashSet<>(); // 创建一个空集
            Set<Integer> first = new HashSet<>(); // 得到第一个元素
            first.add(A[0]);
            newSet.add(nul);
            newSet.add(first);
            return newSet;
        }

        Set<Set<Integer>> oldSet = getSubSets3Core(A, n, cur - 1);
        for (Set<Integer> set : oldSet) {
            newSet.add(set); // 保留原来的
            Set<Integer> clone = (Set<Integer>) ((HashSet) set).clone();
            clone.add(A[cur]);
            newSet.add(clone);
        }
        return newSet;
    }

    public static Set<Set<Integer>> writeByMyself(int[] A, int n, int cur) {
        Set<Set<Integer>> newSet = new HashSet<>();

        if (cur == 0) {
            Set<Integer> nullSet = new HashSet<>();
            Set<Integer> firstSet = new HashSet<>();

            newSet.add(nullSet);
            firstSet.add(A[0]);
            newSet.add(firstSet);
            return newSet;
        }

        Set<Set<Integer>> oldSet = writeByMyself(A, n, cur - 1);
        for (Set<Integer> set : oldSet) {
            newSet.add(set);
            Set<Integer> clone = (Set<Integer>) ((HashSet) set).clone();
            clone.add(A[cur]);
            newSet.add(clone);
        }

        return newSet;
    }

    // 以下是迭代的方法
    public static Set<Set<Integer>> getAns2(int[] A, int n) {
        Set<Set<Integer>> res = new HashSet<>();
        res.add(new HashSet<>()); // res -- > [ [], [1] ]
        // 从第一个元素开始
        for (int i = 0; i < n; i++) {
            Set<Set<Integer>> res_new = new HashSet<>();
            for(Set<Integer> setRes :res){ //
                res_new.add(setRes); // [ [] ]
            }

            for (Set e : res) { // [],[][][][][][]
                Set clone = (Set) ((HashSet) e).clone();
                clone.add(A[i]);//把当前元素加进去
                res_new.add(clone);//把克隆的子集加到大集合中 [[],[1]]
            }
            res = res_new;
        }
        return res;
    }
}
